package leetcode_1001_1100;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class LeeCode_1039_wrong {
    public static void main(String[] args) {
//        System.out.println(minScoreTriangulation(new int[]{1, 2, 3}));
//        System.out.println(minScoreTriangulation(new int[]{3,7,4,5}));
//        System.out.println(minScoreTriangulation(new int[]{1,3,1,4,1,5}));
        System.out.println(minScoreTriangulation(new int[]{5,5,5,4,2,5}));
//        System.out.println(minScoreTriangulation(new int[]{1,1,1,1,1,1}));
    }
    private static int minScoreTriangulation(int[] values) {
        List<Integer> list = new ArrayList<>(values.length);
        for (int i = 0; i < values.length; i++) {
            list.add(values[i]);
        }
        int[] min = new int[]{Integer.MAX_VALUE};
        f(list, 0, min);
        return min[0];
    }
    private static void f(List<Integer> list, int sum, int[] min){
        int len = list.size();
        if (len == 3){
            sum += list.get(0) * list.get(1) * list.get(2);
            min[0] = Math.min(min[0], sum);
            return;
        }
        if (len < 3){
            min[0] = Math.min(min[0], sum);
            return;
        }
        if (len % 2 == 0){
            List<Integer> newL1 = new ArrayList<>();
            int sum1 = getSum(list, sum, len, newL1);
            f(newL1, sum1, min);

            List<Integer> list2 = new ArrayList<>();
            for (int i = 1; i < list.size(); i++) {
                list2.add(list.get(i));
            }
            list2.add(list.get(0));
            List<Integer> newL2 = new ArrayList<>();
            int sum2 = getSum(list2, sum, len, newL2);
            f(newL2, sum2, min);
        }else {
            for (int i = 0; i < len; i++) {
                List<Integer> list1 = new ArrayList<>();
                for (int j = i; j < len; j++) {
                    list1.add(list.get(j));
                }
                for (int j = 0; j < i; j++) {
                    list1.add(list.get(j));
                }
                List<Integer> newL1 = new ArrayList<>();
                int sum1 = getSum(list1, sum, len, newL1);
                f(newL1, sum1, min);
            }
        }
    }

    private static int getSum(List<Integer> list, int sum, int len, List<Integer> newL) {
        int start = 0;
        Set<Integer> set = new HashSet<>();
        while (start + 1 < len){
            if (start + 2 >= len){
                sum += list.get(start) * list.get(start + 1) * list.get(start + 2 - len);
            }else {
                sum += list.get(start) * list.get(start + 1) * list.get(start + 2);
            }
            if (!set.contains(start)) {
                newL.add(list.get(start));
                set.add(start);
            }
            if (start + 2 >= len){
                if (!set.contains(start + 2 - len)) {
                    newL.add(list.get(start + 2 - len));
                    set.add(start + 2 - len);
                }
            }else {
                if (!set.contains(start + 2)){
                    newL.add(list.get(start + 2));
                    set.add(start + 2);
                }
            }
            start += 2;
        }
        return sum;
    }
}
